package 周赛;

import java.util.*;

public class 心算挑战 {

    public int maxmiumScore(int[] cards, int cnt) {
        Arrays.sort(cards);
        int sum = 0;
        int index = cards.length - 1;
        while(cnt > 0){
            sum += cards[index--];
            cnt--;
        }
        if(sum % 2 == 0){
            return sum;
        }
        for(int i = index;i >= 0;i--){
            for(int j = index + 1;j < cards.length;j++){
                sum -= cards[j];
                sum += cards[i];
                if(sum % 2 == 0){
                    return sum;
                }
                sum -= cards[i];
                sum += cards[j];
            }
        }
        return 0;
    }
//排序先取最大的cnt个数，如果它们的和是偶数直接输出，
// 不然就找一个已取的最小的奇数换成剩下未取的最大的偶数，
// 或者找一个已取的最小的偶数换成剩下未取的最大奇数
    public int maxmiumScore2(int[] cards, int cnt) {
        Arrays.sort(cards);
        int sum=0;
        //奇数最小值，偶数最大值。偶数最小值，奇数最大值
        int a=Integer.MAX_VALUE,b=Integer.MIN_VALUE,c=Integer.MAX_VALUE,d=Integer.MIN_VALUE;
        //偶数最大值
        int e=0;
        for (int i = 0; i < cards.length; i++) {
            if (cards[i]%2==0)
               e=Math.max(e,cards[i]);
        }
        if (cnt==1)
            return e;
        for (int i = cards.length-1; i > cards.length-1-cnt ; i--) {
            if (cards[i]%2==0)
                c = Math.min(c, cards[i]);
            else
                a=Math.min(a,cards[i]);
            sum+=cards[i];
        }
        if (cnt==cards.length)
            return sum%2==0?sum:0;
        for (int i = 0; i < cards.length - cnt; i++) {
            if (cards[i]%2==0)
                b=Math.max(b,cards[i]);
            else
                d=Math.max(d,cards[i]);
        }
        if (sum%2==0)
            return sum;
        else
            sum=Math.max(sum-a+b,sum-c+d);
        return sum<0?0:sum;
    }
}
